package suanfa;

import java.io.IOException;
import java.util.*;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2024/8/31-下午1:01
 * Since  :   1.0
 * Version:   1.0
 */
public class Solution4 {

    public static int getNumber(int n) {
        int result = 0;
        while (n > 0) {
            int temp = n % 10;
            result += temp * temp;
            n /= 10;
        }
        return result;
    }


    public static boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        while (!set.contains(n)) {
            set.add(n);
            n = getNumber(n);
            if (n == 1)
                return true;

        }
        return n == 1;

    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (Math.abs(i - map.get(nums[i])) <= k) {
                    return true;
                } else {
                    map.put(nums[i], i);
                }
            } else {
                map.put(nums[i], i);
            }
        }
        return false;
    }

    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }

        int finalResult = 1;
        for (int i : nums) {


            if (!set.contains(i - 1)) {
                int result = 1;
                int curNum = i;
                while (set.contains(curNum + 1)) {
                    curNum++;
                    result++;

                }

                finalResult = Math.max(result, finalResult);

            }
        }
        return finalResult;

    }

    public static List<String> summaryRanges(int[] nums) {
        ArrayList<String> results = new ArrayList<>();
        if (nums.length == 0) {
            return results;
        }
        if (nums[0] == -2147483648) {
            results.add("-2147483648->-2147483647");
            results.add("2147483647");
            return results;
        }


        HashSet<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        for (int i : nums) {
            if (!set.contains(i - 1)) {

                int curNum = i;
                while (set.contains(curNum + 1)) {
                    curNum++;
                }
                if (curNum == i) {
                    results.add("" + i);
                } else {
                    String result = "" + i + "->" + curNum;
                    results.add(result);
                }

            }

        }
        return results;


    }

    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 1)
            return intervals;
        boolean flag = false;
        ArrayList<Integer[]> results = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            for (int j = i + 1; j < intervals.length; j++) {
                int startAfter = intervals[j][0];
                int endAfter = intervals[j][1];
                if (end >= startAfter) {
                    end = endAfter;
                    if (j == intervals.length - 1) {
                        i = intervals.length;

                    }
                } else {
                    i = j - 1;
                    break;
                }

            }

            Integer[] result = new Integer[2];

            result[0] = start;
            result[1] = end;
            results.add(result);

        }
        int length = results.size();
        int finalResults[][] = new int[length][2];
        int temp = 0;
        for (Integer[] arr : results) {
            finalResults[temp][0] = arr[0];
            finalResults[temp][1] = arr[1];
            temp++;
        }
        return finalResults;


    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }

        return stack.isEmpty();


    }

    public static int binarySearch(int arr[],int target){
        int left=0;
        int right=arr.length-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (target>arr[mid]) {
                left=mid+1;
            }else if (target<arr[mid]){
                right=mid-1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    public static String simplifyPath(String path) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < path.length(); i++) {
            char c = path.charAt(i);


            if (c == '/') {

                if (stack.isEmpty()){
                  stack.push('/');
                }else {
                    char before = stack.pop();
                    if (before == '/') {
                        stack.push(before);
                    } else {
                        stack.push(before);
                        stack.push('/');
                    }

                }

            } else if (c == '.') {


                    if ((i + 1) < path.length() && path.charAt(i + 1) == '.') {
                        if ((i + 2) < path.length() && path.charAt(i + 2) == '.') {
                            stack.push('.');
                            stack.push('.');
                            stack.push('.');
                            i+=2;
                        }
                        //second .
                        else if (((i+2)<path.length()&&path.charAt(i+2)=='/'&&path.charAt(i-1)=='/')||((i+1)==path.length()-1&&path.charAt(i-1)=='/' ) ){
                            int count=2;
                            while (count > 0) {
                             if (stack.pop()=='/'){
                                 if (stack.isEmpty()){
                                  stack.push('/');
                                 }
                                 count--;
                             }

                            }
                            i+=1;

                        }else {
                            stack.push('.');
                            stack.push('.');
                            i=i+1;

                        }
                    }
                    //first .
                    else if (( (i+1)<path.length()&&path.charAt(i+1)=='/'&&path.charAt(i-1)=='/')||((i)==path.length()-1&&path.charAt(i-1)=='/' )){
                        stack.pop();
                        if (stack.isEmpty()){
                            stack.push('/');
                        }


                    }else {
                        stack.push('.');
                    }


            } else {

                stack.push(c);
            }

        }



        char temp=stack.pop();
        if (temp!='/'){
            stack.push(temp);
        }else {
            if (stack.isEmpty()){
                stack.push(temp);
            }
        }
        StringBuffer stringBuffer = new StringBuffer();
        Iterator<Character> iterator = stack.iterator();
        while (iterator.hasNext()){
            char c=iterator.next();
            stringBuffer.append(c);
        }

        return stringBuffer.toString();


    }

    public static void main(String[] args) {
//        int n=19;
//        System.out.println(isHappy(19));
//        int nums[] = {1, 0, 1, 1};
//        int k = 1;
//        System.out.println(containsNearbyDuplicate(nums, k));
//       int [] nums = {-2147483648,-2147483647,2147483647};
//        List<String> list = summaryRanges(nums);
//        for(String s:list){
//            System.out.print(s);
//            System.out.print(" ");
//        }

//        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
//        int[][] intervals = {{1, 4}, {4, 5}};
//        int[][] merge = merge(intervals);
//        for(int[] arr:merge){
//            System.out.print(arr[0]+" ");
//            System.out.print(arr[1]);
//            System.out.println();
//        }

//        String s = "([])";
//        System.out.println(isValid(s));

//        String s ="/hello../world";
//        System.out.println(simplifyPath(s));
//        byte a=127;
//        byte b=127;
//        short c=125;
//
//        b+=a;
//        System.out.println(b);
//        Solution4 solution4 = new Solution4();
//        try {
//            Object clone = solution4.clone();
//        } catch (CloneNotSupportedException e) {
//            throw new RuntimeException(e);
//        }
//        ArrayList<Object> objects = new ArrayList<>();
        int []arr={2,4,5,6,7,8,9,11};
        System.out.println(binarySearch(arr,12));

    }
}
